/**
 * @author hewei
 * @version 1.0
 * @description: 1026. 节点与其祖先之间的最大差值
 * @date 2022/10/20 19:38
 */

public class MaxAncestorDiff {

    int ans = 0;
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }

    public int[] process(TreeNode node) {
        if (node == null) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
        int[] l = process(node.left);
        int[] r = process(node.right);
        if (l[0] != Integer.MAX_VALUE) ans = Math.max(ans, Math.max(Math.abs(node.val - l[0]), Math.abs(node.val - l[1])));
        if (r[0] != Integer.MAX_VALUE) ans = Math.max(ans, Math.max(Math.abs(node.val - r[0]), Math.abs(node.val - r[1])));
        return new int[]{Math.min(node.val, Math.min(l[0], r[0])), Math.max(node.val, Math.max(r[1], l[1]))};
    }

    public int dfs(TreeNode node, int max, int min) {
        if (node == null) return max - min;
        max = Math.max(node.val, max);
        min = Math.min(node.val, min);
        return Math.max(dfs(node.left, max, min), dfs(node.right, max, min));
    }
}
